
import java.util.HashMap;
import java.util.Map;

public class Solution {
    public boolean isValid(String s) {
        //1.字符串长度为奇数是，直接返回false
        int size = s.length();
        if (size % 2 == 1)
            return false;
        //2.使用哈希表存储，右括号为key （、{、[, 左括号为 value ）、]、}
        Map<Character, Character> pairs = new HashMap<>();
        pairs.put(')', '(');
        pairs.put(']', '[');
        pairs.put('}', '{');
        Stack<Character> stack = new ArrayStack<>();
        for (int i = 0; i < size; i++) {
            char c = s.charAt(i);
            //3.如果是左括号
            if (pairs.containsKey(c)) {
                //3.1 如果栈为空，或栈不为空时栈顶元素和当前元素不匹配，则返回 false
                if (stack.isEmpty() || stack.peek() != pairs.get(c)) {
                        return false;
                } else {
                    //3.2 如果栈不为空，且栈顶元素和当前元素匹配，栈顶元素出栈
                   stack.pop();
                }

            } else {
                //4.如果是右括号，入栈
                stack.push(c);
            }
        }
        //5.判断栈是否为空，为空返回true，否则返回false
        return stack.isEmpty();
    }

    public static void main(String[] args) {
        System.out.println(new Solution().isValid("()"));
        System.out.println(new Solution().isValid("()[]{}"));
        System.out.println(new Solution().isValid("(]"));
        System.out.println(new Solution().isValid("){"));
    }
}
